package stack;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author: 26233
 * @create: 2022-07-31 15:33:01
 * @Description
 *
 * 单调栈：
 *   定义：栈中的元素满足递增或者递减规律，分为单调减、单调增
 *   用处：在求元素左右位置最近的最大，最小值/位置
 *
 *   问题：对于给定的整数数组nums，找到每个元素右侧第一个比自己大的数的下标，如果没有，填-1
 * example:
 * input:[2, 1, 5, 6, 2, 3, 1]
 * output:[2, 2, 3, -1, 5, -1, -1]
 **/

public class MonotonousStack {

    public int[] solution(int[] input){

        int[] r = new int[input.length];
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> index = new Stack<>();
        for (int i = 0; i < input.length; i++) {
            if (stack.isEmpty() || input[i] <= stack.peek()) {
                stack.push(input[i]);
                index.push(i);
                continue;
            }
            while (!stack.isEmpty() && stack.peek() < input[i]) {
                stack.pop();
                r[index.pop()] = i;
            }
            stack.push(input[i]);
            index.push(i);
        }

        while (!index.isEmpty()){
            r[index.pop()] = -1;
        }

        return r;
    }

    public static void main(String[] args) {
        int[] input = {2, 1, 5, 6, 2, 3, 1};
        int[] solution = new MonotonousStack().solution(input);
        System.out.println("solution = " + Arrays.toString(solution));
    }

}
